﻿// 0904train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
 构造数列，第一个数为n，后面的数不大于前一个的一半，
 数列奇偶相间或者全为奇数或者全为偶数，数列的元素都是正整数，能构造多少数列

输入描述
输入一个n

输出描述
输出可以构造的序列个数

输入
7
输出
6
可以构成 [7], [7,3], [7,2], [7,1], [7,3,1], [7,2,1]
 */
class Solution01
{
public:
    int dpSame(int num)
    {
        //每个序列至少有它本身
        vector<int>dynamic_vec(num + 1, 1);
        //计算奇偶相同的序列
        //判断num是奇数还是偶数，决定i的起始位置是1还是2
        int start = 1;
        if (num % 2 == 0) start = 2;
        //+=2保证奇偶相同
        for (int i=start; i<=num; i+=2)
        {
            //i>=2*j，那么j只能接到
            for (int j=start; j<=i/2; j+=2)
            {
                dynamic_vec[i] += dynamic_vec[j];
            }

        }
        return dynamic_vec[num];
    }
    int dpDifferent(int num)
    {
        vector<int>dynamic_vec(num + 1, 1);

        for (int i=1; i<=num; i++)
        {
            //j的跟i奇偶相反
            int start = 1;
            if (i % 2 == 1) start = 2;
            for (int j=start; j<=i/2; j+=2)
            {
                dynamic_vec[i] += dynamic_vec[j];
            }
        }

        return dynamic_vec[num];
    }
    Solution01(int num)
    {
        //[1,2,7]这样看，后面的数>=2*前面的数，就是说，j最多接到j<=i/2的位置
        //全奇全偶序列 j跟i必须奇偶相同
        //奇偶相间序列，j跟i奇偶相反
        
        //因为这两个序列都包含{num}这个数列，所以要减去一个
        int same = dpSame(num);
        int different = dpDifferent(num);
        int result = same + different - 1;
        cout << result;
        //Solution01
    }
};


/*
 定义字符串完全由"A"和"B"组成，当然也可以全是"A"或全是"B"
 如果字符串从前往后都是以字典序排列的，那么我们称之为严格递增字符串
给出一个字符串 s，允许修改字符串中的任意字符，
即可以将任何的"A"修改成"B"，也可以将任何的"B"修改成"A"，
求可以使 s 满足严格递增的最小修改次数。存在0 < len(s) < 100000
输入描述
输入一个字符串，表示原始字符串
输出描述
输出一个数字，表示将原始字符串修改为严格递增字符串的最少修改次数

输入
AABBA
输出
1
修改最后一位"A"为"B"，字符串会变为"AABBB"
 */
class Solution02
{
public:
    Solution02(string&origin_str)
    {
        int s_size = origin_str.size();
        vector<vector<int>>dynamic_vec(s_size, vector<int>(2));

        if (origin_str[0]=='A')
        {
            dynamic_vec[0][0] = 0;
            dynamic_vec[0][1] = 1;
        }
        else if (origin_str[0] == 'B')
        {
            dynamic_vec[0][0] = 1;
            dynamic_vec[0][1] = 0;
        }

        //dp[i][0] curr_char翻转为A需要的最小次数
        //dp[i][1] curr_char翻转为B
        for (int i=1; i< s_size; i++)
        {
            char curr_char = origin_str[i];
            if (curr_char=='A')
            {
                //curr_char为A
                //这里不需要翻转，上一个字符必须是A，不然不可能构成单调增序列
                dynamic_vec[i][0] = dynamic_vec[i - 1][0];

                //翻转成B，前面可以是A，也可以是B
            	//前面翻转的次数取最小值
                dynamic_vec[i][1] = min(dynamic_vec[i - 1][0], dynamic_vec[i - 1][1]) + 1;
            }
            else
            {
                //curr_char为B
                //B翻转成A，前面必须是A
                dynamic_vec[i][0] = dynamic_vec[i - 1][0] + 1;
                //这里已经是B，不需要翻转了
                //B前面可以是A，也可以是B
                dynamic_vec[i][1] = min(dynamic_vec[i - 1][0], dynamic_vec[i - 1][1]);
            }

        }
        cout << min(dynamic_vec[s_size - 1][0], dynamic_vec[s_size - 1][1]);
        //Solution02
    }
};

int main()
{
    //string origin_str = "ABABBA";
    string origin_str;
    getline(cin, origin_str);
    Solution02 solu(origin_str);
    //Solution01 solu(7);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
